package com.damin.liuxiaojing;

import lombok.Data;

public class TreeSelectSort {
    public static void sort(int[] r) {
        int length = r.length;
        // 根据待排序序列的结点个数，计算胜者树的叶子结点个数，该个数必须是2的幂
        int leafSize = 1;
        while (leafSize < length) {
            leafSize *= 2;
        }
        // 计算胜者树的所有节点数，叶子结点存放的起始位置
        int treeSize = 2 * leafSize - 1;
        int loadIndex = leafSize - 1;

        TreeNode[] tree = new TreeNode[treeSize];// 胜者树结点数组
        // 把待排序结点复制到胜者树的叶子结点中,并补足外结点
        int j = 0;
        for (int i = loadIndex; i < treeSize; i++) {
            tree[i] = new TreeNode();
            tree[i].setIndex(i);
            if (j < length) {
                tree[i].setActive(true);
                tree[i].setData(r[j++]);
            } else {
                tree[i].setActive(false);
            }
        }
        // 产生胜者树查找最小结点
        int i = loadIndex;
        // 处理每层节点
        while (i > 0) {
            // 处理各对比赛者
            j = i;
            while (j < 2 * i) {
                // 右孩子失活，或左孩子较小
                if (!tree[j + 1].active || (tree[j].getData() <= (tree[j + 1].getData()))) {
                    tree[(j - 1) / 2] = tree[j]; // 左孩子(胜者)赋值给父结点
                } else {
                    tree[(j - 1) / 2] = tree[j + 1]; // 右孩子(胜者)赋值给父结点
                }
                j += 2; // 下一对比赛者
            }
            i = (i - 1) / 2; // 处理上层结点
        }
        // 将最小结点存入序列r的第一个位置
        r[0] = tree[0].getData();
        //
        for (i = 1; i < length; i++) { // 处理剩余的n-1个记录
            updateTree(tree, tree[0].getIndex()); // 调整胜者树
            r[i] = tree[0].getData(); // 将胜者树的根(最小者)存入数组r
        }
    }

    // i是当前最小关键字记录的下标
    private static void updateTree(TreeNode[] tree, int index) {
        tree[index].setActive(false); // 该元素相应外结点不再比赛
        if (index % 2 == 0) { // i为偶数，对手为左结点
            tree[(index - 1) / 2] = tree[index - 1];
        } else { // i为奇数，对手为右结点
            tree[(index - 1) / 2] = tree[index + 1];
        }
        index = (index - 1) / 2; // 最小元素输出后，其对手上升到父结点
        int opponentIndex;
        while (index > 0) { // 直到index==0
            if (index % 2 == 0) { // i为偶数，对手为左结点
                opponentIndex = index - 1;
            } else { // i为奇数，对手为右结点
                opponentIndex = index + 1;
            }
            // 比赛对手中有一个为空
            if (!tree[opponentIndex].active
                || (tree[index].active && tree[index].getData() <= tree[opponentIndex].getData())) {
                tree[(index - 1) / 2] = tree[index];
            } else {
                tree[(index - 1) / 2] = tree[opponentIndex];
            }
            index = (index - 1) / 2; // 上升一层
        }
    }

    public static void display(int[] r) {
        for (int item : r) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] r = new int[] {3, 5, 5, 4, 120, 43, 1, 76, 78, 12, 346};
        TreeSelectSort.sort(r);
        TreeSelectSort.display(r);
    }

    @Data
    static class TreeNode { // 胜者树的结点类
        private int data; // 排序记录结点数据值
        private int index; // 结点在满二叉树中的序号
        private boolean active; // 参加选择标志，1表示参选，0表示不参选
    }
}
